\chapter[Automata and Formal Languages \\ \textnormal{\emph{Lectured in Michaelmas \oldstylenums{2022} by \textsc{Prof.\ B.\ L\"owe}}}]{Automata and Formal Languages}
\emph{\Large Lectured in Michaelmas \oldstylenums{2022} by \textsc{Prof.\ B.\ L\"owe}}

Computation, or computability, is central to modern mathematics.
However, we very rarely think about the precise definition of what it means for something to be `computable'.
There is an important difference between existence and algorithmic access to a witness.
In this course, we discuss the precise definition of computability, and use it to prove that there is no algorithm to solve certain problems.

There are many possible ways to define computation and computability, and it is a remarkable fact that most `reasonable' definitions of computable functions coincide.
This is known as the Church--Turing thesis, and it allows us to reason about computation without being tied to a specific model, such as register machines, the Turing machine, or Church's recursive functions.

A language is a set of strings called words.
Languages can be used to model countable sets, such as the set of powers of two, the set of primes, or the set of numbers which describe a register machine that determine if a given computation will halt or not.
We will explore different types of language, and use computation theory to study which properties of languages can be determined algorithmically.
We prove that there is a large class of languages for which there is an algorithm to determine if a given word lies in the language, but a much smaller class of languages for which we can determine algorithmically if they contain any words at all.

\subfile{../../ii/afl/main.tex}
